Galois Counter Mode-Advanced Encryption Standard (GCM-AES) is widely applied to the IPsec environment. The second layer security standard MACsec of Ethernet also uses GCM-AES algorithm as the default encryption/decryption. GCM-AES algorithm uses Galois Field GF(2128) multiplication to realize the hash function, resulting in the increase of the hardware cost of GCM-AES in hardware implementation. The hardware cost of a single GF(2128) multiplier is near the cost of a 128-bit AES core engine. When integrating the MACsec controller having GCM-AES to the Ethernet MAC controller, the cost ratio affected by GCM-AES will be even higher.
GF(2n) is a finite field, a space defined by an n-order primitive polynomial, with 2n elements. Each element is n-bit, and n bits are the coefficients of the polynomial of the corresponding element:b0+b1x+ . . . +bn−1xn−1 where bi is an element in GF(2), either 0 or 1. Assume that the primitive polynomial constructing the GF(2n) space is g(x), the multiplication of GF(2n) elements may be seen as two steps: first, two elements go through a general polynomial multiplication; then, the obtained polynomial in the first step is divided by g(x) to obtain the remainder. The addition of GF(2n) elements is logically the same as the n-bit XOR operation.
When n is a large positive integer, such as 128, the GF(2n) multiplication is an expensive computation. Therefore, a composite field is used to reduce the computation complexity. The mathematic expression for composite field is GF((2m)k), where k*m=n, and both m and k are positive integers. In terms of the number of bits of elements, the composite field is to translate an n-bit element in GF(2n) to k m-bit elements in GF(2m). Because k*m=n, the entire result is still an n-bit value. In the composite field, GF(2m) is called a ground field. To map an element from GF(2n) to GF((2m)k), three polynomials are required, including g(x) required to construct GF(2n), an m-order primitive polynomial p(x) and a k-order primitive polynomial r(x), where the coefficients of p(x) belong to GF(2), and the coefficients of r(x) belong to GF(2m).
Then, by using the theory proposed by Christof Paar, an n×n matrix M may be found to map elements from GF(2n) to GF((2m)k). The inverse matrix M−1 will map the elements from GF((2m)k) to GF(2n). In the polynomial representation, A element in GF(2n) is represented as:A(x)=a0+a1x+. . . +an−1xn−1ai∈GF(2)After being mapped to composite field GF((2m)k), A may be represented by:A(x)=a0+a1x ai∈GF(2)The composite field multiplication is the same as the aforementioned two steps, first, a general polynomial multiplication followed by obtaining of a remainder.
There are numerous disclosed techniques for Galois Field multipliers (GF multiplier). For example, U.S. Pat. No. 4,251,875 disclosed a generic GF multiplier architecture. By using a single GF(2m) multiplier architecture, the two operands are sequentially inputted to complete the GF(2n) multiplication, where m is a multiple of n. U.S. Pat. No. 7,113,968 disclosed a GF multiplier architecture using a polynomial and two operations of polynomial modulo.
U.S. Pat. No. 7,133,889 disclosed a GF multiplier architecture, as shown in FIG. 1, using a single ground field GF(2m) multiplier architecture and using Karatsuba-Ofman computation for multiplication. U.S. Pat. No. 6,957,243 disclosed a GF multiplier architecture using polynomial factoring approach, by inputting an operand A(x) sequentially, i.e., A0(x), A1(x), . . . ,AT−1(x) sequentially, and inputting another operand b(x) in parallel, to perform multiplication, as shown in FIG. 2.
In recent years, GF(2n) is widely applied to error-control code (ECC) and encryption, such as Reed-Solomon, Cyclic Code in ECC, and Ellipse curve encryption system, AES, and GCM in encryption. Hence, it is imperative to devise a GF multiplier hardware architecture to reduce the GCM-AES cost, maintain Gigabit processing power and suit the network communication environment.